package com.yubest;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * <p>
 * 进阶：
 * <p>
 * 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
 *
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * 示例 2：
 * <p>
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 * 示例 3：
 * <p>
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 *
 * <p>
 * 提示：
 * <p>
 * 0 <= nums.length <= 10^5
 * -10^9 <= nums[i] <= 10^9
 * nums 是一个非递减数组
 * -10^9 <= target <= 10^9
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/18 17:35
 */
public class P0034 {
}

class Solution34 {

    /**
     * 思路：先二分查找到符合的一个数，然后用双指针，从当前位置往两边移动，确定边界
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int index = indexOf(nums, 0, nums.length - 1, target);
        if (index == -1) {
            return new int[]{-1, -1};
        }
        int p1 = index, p2 = index;
        boolean isMove;
        do {
            isMove = false;
            if (p1 - 1 >= 0 && target == nums[p1 - 1]) {
                p1--;
                isMove = true;
            }
            if (p2 + 1 < nums.length && target == nums[p2 + 1]) {
                p2++;
                isMove = true;
            }
        } while (isMove);
        return new int[]{p1, p2};
    }

    public int indexOf(int[] nums, int start, int end, int target) {
        if (start < 0 || end < 0 || start > end) {
            return -1;
        }
        int m = (start + end) / 2;
        if (nums[m] == target) {
            return m;
        }
        return target > nums[m] ? indexOf(nums, m + 1, end, target) : indexOf(nums, start, m - 1, target);
    }
}
